package leetcode101.dynamic_planning;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code13
 * @Description 474. 一和零
 * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
 *
 * 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
 *
 * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
 * 输出：4
 * 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
 * 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
 * 示例 2：
 *
 * 输入：strs = ["10", "0", "1"], m = 1, n = 1
 * 输出：2
 * 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
 *  
 *
 * 提示：
 *
 * 1 <= strs.length <= 600
 * 1 <= strs[i].length <= 100
 * strs[i] 仅由 '0' 和 '1' 组成
 * 1 <= m, n <= 100
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-15 9:28
 */
public class Code13 {
    public static void main(String[] args) {
        String[] strs = new String[]{"0","0","0","0","0","1","1","0","1","1","1","0","1","0","1","1","0","0","1","0","1","1","0","1","1","1","1","1","0","1","1","1","1","1","1","0","1","1","0","0","0","0","1","1","0","1"};
        System.out.println(findMaxForm(strs, 52, 12));
    }

    public static int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        int zero; // 记录字符串中有几个"0"
        int one; // 记录字符串中有几个"1"

        for (int i = 1; i < dp.length; i++) {
            /*
             为什么针对多维度的背包问题维数要从1开始？
             因为你要考虑全是 1 不匹配 0
             或者说全是 0 不考虑 1 的情况
             */
            for (int j = 0; j < dp[0].length; j++) {
                for (int k = 0; k < dp[0][0].length; k++) {
                    // 先把上一行抄下来
                    zero = countZero(strs[i - 1]);
                    one = strs[i - 1].length() - zero;
                    if (j >= zero && k >= one) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zero][k - one] + 1);
                    } else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

    public static int countZero(String str) {
        int temp = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                temp++;
            }
        }
        return temp;
    }

//    public static int findMaxForm(String[] strs, int m, int n) {
//        int[][] dp = new int[m + 1][n + 1];
//        for (String s: strs) {
//            int[] count = countzeroesones(s);
//            for (int zeroes = m; zeroes >= count[0]; zeroes--)
//                for (int ones = n; ones >= count[1]; ones--)
//                    dp[zeroes][ones] = Math.max(1 + dp[zeroes - count[0]][ones - count[1]], dp[zeroes][ones]);
//        }
//        return dp[m][n];
//    }
//    public static int[] countzeroesones(String s) {
//        int[] c = new int[2];
//        for (int i = 0; i < s.length(); i++) {
//            c[s.charAt(i)-'0']++;
//        }
//        return c;
//    }

}
/*
思路一：先根据字符串的长度进行排序
之后使用贪心策略挨个遍历
但是这样无法通过用例{"111","1000","1000","1000"}, 9, 3
思路二：使用动态规划
这道题相当于多维度的背包问题
dp[i][j][k]代表了前 i 个字符串中在构成 j 个 0 和 k 个 1 的的前提下的最多字符串个数
那么dp[i][j][k]等于
Max{dp[i - 1][j][k], dp[i - 1][j - strs[i - 1].0][k - strs[i - 1].1] + 1}
 */

/*
思路一：
public static int findMaxForm(String[] strs, int m, int n) {
        quickSort(strs, 0, strs.length - 1);
        int ans = 0, zero;
        for (String str : strs) {
            zero = countZero(str);
            if (zero <= m && str.length() - zero <= n) {
                ans++;
                m -= zero;
                n -= (str.length() - zero);
            }
            if (m <= 0 && n <= 0) break;
        }
        return ans;
    }

    public static void quickSort(String[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, 0, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    public static int partition(String[] arr, int low, int high) {
        String temp = arr[low];
        while (low < high) {
            while (low < high && arr[high].length() >= temp.length()) high--;
            arr[low] = arr[high];
            arr[high] = temp;
            while (low < high && arr[low].length() <= temp.length()) low++;
            arr[high] = arr[low];
            arr[low] = temp;
        }
        return low;
    }

    public static int countZero(String str) {
        int temp = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') temp++;
        }
        return temp;
    }
 */

/*
思路二：使用三维dp的话会出现很多个0很多个1，用例过了94%
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        int zero = 0; // 记录字符串中有几个"0"
        int one = 0; // 记录字符串中有几个"1"

        for (int i = 1; i <= strs.length; i++) {
            if (strs[i - 1].length() == 1) {
                if (strs[i - 1].charAt(0) - '0' == 0) {
                    zero++;
                    if (zero <= m) {
                        for (int j = 1; j < dp.length; j++) {
                            dp[j][zero][0] = zero;
                        }
                    }
                } else {
                    one++;
                    if (one <= n) {
                        for (int j = 1; j < dp.length; j++) {
                            dp[j][0][one] = one;
                        }
                    }
                }
            }
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                for (int k = 1; k < dp[0][0].length; k++) {
                    zero = countZero(strs[i - 1]);
                    one = strs[i - 1].length() - zero;
                    if (zero <= j && one <= k) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zero][k - one] + 1);
                    } else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

    public static int countZero(String str) {
        int temp = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') temp++;
        }
        return temp;
    }
 */

/*
思路三：官方题解，二维dp
dp[i][j] 代表了用 i 个 0 和 j 个 1 能组成最多的字符串个数
dp[i][j] = Math.max(1 + dp[i - strs[i - 1].0][j - strs[i - 1].1], dp[i][j])
 */